package demo.DataStrucAndAlgo.Stack;
import java.util.Arrays;

/**
 * @Auther: vanse(lc))
 * @Date: 2022/7/25-07-25-10:01
 * @Description：数组实现栈
 */
// 栈: 类型
// 数组: 类型
// 链表
// 类型和类型的关系
// 继承 类继承一个类 int[]
// 组合关系 类中包含类
public class StackByArray {
    // 组合关系
    int[] arr; // 底层用数组实现
    // 栈顶(指针) === 栈的变化
    int top; // 默认栈中没有值
    // 无参构造器
    public StackByArray(){
        this(10); // this放第一行
        top = -1;
    }
    //new StackByArray(10);
    public StackByArray(int initialCapacity){
        arr = new int[initialCapacity];
    }
    // 增强量
    public StackByArray(int initialCapacity, int capacityIncrement){

    }
    //push:压栈 将值放入栈中
    public void push(int value) {
        // TODO 数组越界
        // 集合: 扩容 (本质上: 换一个新的容量数组)
        if(isFull()){
            // 定义新数组 把原数组的内容拷贝到新数组
            // 扩容2 arr.length << 1
            // 扩容1.5 arr.length + (arr.length >> 1)
            arr = Arrays.copyOf(arr,arr.length << 1);
        }

        // top++; // top=0
        arr[++top] = value; //arr[0] = 0

    }

    //pop:弹栈 将栈顶数据弹出(假删除)
    // 本质上是top往下移动
    public int pop() {
//        int value = arr[top];
//        top-- ;
//        return value; // 栈顶值

        if(isEmpty()){
            // 模拟基类写法: 找不到值 就返回-1
            //return -1;  // 没有返回值 才能结束方法
            // 抛异常
            throw new RuntimeException("栈中没有元素");
        }
        return arr[top--];
    }

    // 遍历栈
    public void show() {
        System.out.println("--栈顶--");
        // top -> 0
        for (int i = top; i >= 0; i--) {
            System.out.println(arr[i]);
        }
        System.out.println("--栈底--");
    }

    // 查看栈顶元素 不弹
    public int peek() {
        if(isEmpty()){
            // 模拟基类写法: 找不到值 就返回-1
            //return -1;  // 没有返回值 才能结束方法
            // 抛异常
            throw new RuntimeException("栈中没有元素");
        }
        return arr[top];
    }

    // 栈的容量
    public int getSize() {
        // -1 + 1
        return top + 1;  // top = 0(索引)
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public boolean isFull() {
        return top == arr.length - 1;
    }

    //    public void grow(){}
    public static void main(String[] args) {
        StackByArray sba = new StackByArray();
        sba.push(0);
        sba.push(5);
        sba.push(4);
        sba.push(9);
        sba.push(7);
        sba.push(12);
        System.out.println("栈容量: " + sba.getSize());
//        sba.pop();
//        sba.show(); // 遍历
//        System.out.println("弹栈: " + sba.pop());
//        sba.show(); // 遍历
//        // 查看栈顶
//        System.out.println(sba.peek());
    }
}
